package leetcode100

// TODO 递归 [经典] 【-】 二叉树的直径
// TODO https://leetcode.cn/problems/diameter-of-binary-tree/solution/go-yu-yan-ji-jian-by-intelligent-shterng-gpj2/

func diameterOfBinaryTree(root *TreeNode) int {
	var res int
	var dfs func(*TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		// 计算每个结点左右孩子的高度
		left := dfs(node.Left)
		right := dfs(node.Right)

		// 路径长度等于左右孩子高度之和
		if left+right > res {
			res = left + right
		}

		// 返回较高的结点作为本结点的高度
		if left > right {
			return left + 1
		}

		return right + 1
	}

	dfs(root)
	return res
}
